#include <string>
#include <vector>
#include <unordered_map>
// https://leetcode.cn/problems/minimum-window-substring/?envType=study-plan-v2&envId=top-100-liked
using namespace std;
// 思路：使用滑动窗口
/**
 * 1. 使用两个指针left和right表示窗口的左右边界，初始时都指向字符串s的起始位置
 * 2. 使用一个哈希表match_map记录字符串t中每个字符及其出现的次数
 * 3. 使用另一个哈希表window_map记录当前窗口中每个字符及其出现的次数
 * 4. 使用变量have记录当前窗口中已经满足目标字符计数的字符种类数，使用变量tCount记录目标字符种类数
 * 5. 移动right指针扩展窗口，直到窗口中包含了字符串t中的所有字符
 * 6. 当窗口中包含了字符串t中的所有字符时，尝试移动left指针收缩窗口，直到窗口中不再包含字符串t中的所有字符
 * 7. 在每次收缩窗口时，更新最小覆盖子串的起始位置和长度
 * 8. 重复步骤5-7，直到right指针到达字符串s的末尾
 * 9. 返回最小覆盖子串
 * 时间复杂度：O(n) 其中n是字符串s的长度，最坏情况下每个字符都被访问两次（一次由right指针，一次由left指针）
 */
class Solution
{
public:
    string minWindow(string s, string t)
    {
        unordered_map<char, int> window_map; // 窗口内字符计数
        unordered_map<char, int> match_map;  // 目标字符计数
        int tCount = 0;                      // 目标字符种类数
        int have = 0;                        // 窗口内已满足目标字符种类数
        int left = 0, right = 0;             // 窗口左右指针
        int resStart = 0;                    // 结果子串起始位置
        int resLen = INT32_MAX;              // 结果子串长度
        // 1. 构建目标字符计数map
        for (auto c : t)
        {
            ++match_map[c];
        }
        tCount = match_map.size();
        // 2. 计算目标字符种类数
        while (right < s.size())
        {
            // 1）. 判断当前right字符是否在目标字符中
            if (match_map.count(s[right]))
            {
                ++window_map[s[right]];
                // 判断当前字符计数是否满足目标字符计数
                if (window_map[s[right]] == match_map[s[right]])
                {
                    ++have;
                }
            }
            // 2). 判断当前窗口的字符种类数是否满足目标字符种类数 have == tCount
            while (have == tCount)
            {
                // 1)) 更新结果字符串
                if (right - left + 1 < resLen) // 为什么是right - left + 1？ 因为right和left都是索引
                {
                    resStart = left;
                    resLen = right - left + 1;
                }
                // 2)). 尝试收缩窗口 移动left指针
                if (match_map.count(s[left]))
                {
                    --window_map[s[left]];
                    // 如果当前字符计数不满足目标字符计数
                    if (window_map[s[left]] < match_map[s[left]])
                    {
                        --have;
                    }
                }
                ++left;
            }
            // 3). 扩展窗口 移动right指针
            ++right;
        }
        return s.substr(resStart, resLen == INT32_MAX ? 0 : resLen);
    }
};